iT邦幫忙

2022 iThome 鐵人賽
DAY 23
0
自我挑戰組

玩game學打code。街機程式設計再進化。微軟Arcade系列 第 23 篇

Arcade也能學演算法Ouo!? 演算法遊戲!(4)

14th鐵人賽 ａrcade 運算思維 遊戲設計 程式設計
682 瀏覽

  • 分享至 

  • xImage
    •  

第四篇：棋類遊戲-黑白棋演算法篇

大綱

  • 遊戲內容
  • 關於黑白棋的規則
  • 確認可以連線
  • 連線後?
  • 結束了?
  • 範例程式

遊戲內容


(此畫面是由空白網頁執行javascript，可以根據需求改造成nodejs讓其可以在本機執行)
輸入位置後下棋
然後更新棋盤

關於黑白棋的規則

黑白棋下棋的規則

  1. 影響棋子的方式是 由兩個同色的棋子包夾，則中間的棋子被同化。
  2. 每次下棋必須影響對方至少一顆旗子
  3. 如果你無法下棋的話，你該局就pass
  4. 如果雙方都無法下棋則結束遊戲，場上棋多者勝

如何確認連線

思路:

  1. 往八個方向搜尋，如果搜尋到對手的棋再搜到自己的棋則為可行的方位
  2. 為了節省時間，我們增加條件式:如果往外找的時候發現此位置不是對手的棋
    (自己的棋/沒有棋)那這個方位就不成立，所以直接跳出迴圈

想好之後就上程式碼!!

function check_put_legitimate(X, Y, turn){

我預設需要的參數有 現在的位置(X,Y)跟現在是誰的回合(turn)

function check_put_legitimate(X, Y, turn){
    let check = turn == "O" ? "X" : "O";
    let legitimate = false;

let check = turn == "O" ? "X" : "O";
我將白色用O黑色用X標記
所以我如果turn是O check就要是X 反之亦然
legitimate 是之後要回傳的值代表是否成立
接下來就是搜尋的部分
還記的我們上一次八個方位洋洋灑灑寫了快80行嗎
我們今天就要來優化搜尋的部分
大家可以發現我們搜尋的部分就很簡單
基本上就是某個值再加減 然後判斷
所以其實真正再變的是要不要加減
通過這個想法我們可以來做一個列表來裝這些東西

let search_mode = [
    [0, 1], [1, 0], [0, -1], [-1, 0], // down, right, up, left
    [1, 1], [1, -1], [-1, 1], [-1, -1] // down-right, down-left, up-right, up-left
]

我們建立後列表後在裡面再創一個列表放置Y跟X要加減的值
例如 如果往上找X-- Y不用動 所以[0, -1]
剩下就以此類推
有了搜尋模式後 我們只要依序餵給迴圈就好

    for(let i = 0; i < search_mode.length; i++){ // mode
        let x = X + search_mode[i][0];
        let y = Y + search_mode[i][1];
        ...
        while (x>=0 && x<=7 && y>=0 && y<=7){
            if(Data[y][x] == check){
                ...
                x += search_mode[i][0];
                y += search_mode[i][1];
            ...
        }

這樣就完成簡單的縮減了
然後是判斷式
我們前面提到如果不成立合法方位的話就跳出迴圈
可是如果找玩了的話也要跳出迴圈阿
我怎麼知道我有沒有成功找到呢
所以我先宣告一個變數check_legitimate還有check_count紀錄中間連線的次數方便之後要判斷用

    for(let i = 0; i < search_mode.length; i++){
        let x = X + search_mode[i][0];
        let y = Y + search_mode[i][1];
        let check_count = 0;
        let check_legitimate = false;
        ...

接下來就是搜尋了

        ...
        while (x>=0 && x<=7 && y>=0 && y<=7){
            if(Data[y][x] == check){
                check_count++;
                x += search_mode[i][0];
                y += search_mode[i][1];
            }else if(Data[y][x] == turn && check_count > 0){
                check_legitimate = true;
                break;
            }else{
                break;
            }
        }
        ...

如果找到對方的棋子就繼續找，並且計數加一
阿如果找到對方的棋子還有一個可能
那就是找到自己的
那找到自己的話還要看中間有沒有對手的棋子
所以我們要看所以我們要看check_count有沒有大於0
如果大於0也就是說有夾棋子然後找到自己的棋子
所以這個方向是成立的
那麼我就紀錄方位的代碼跟我夾了幾個棋子方便之後利用的時候不用再跑一次判斷
最後 如果都沒有成立 代表這個方向是不合法的 就直接跳離迴圈
最後判斷式會長這樣

    for(let i = 0; i < search_mode.length; i++){
        let x = X + search_mode[i][0];
        let y = Y + search_mode[i][1];
        let check_count = 0;
        let check_legitimate = false;
        while (x>=0 && x<=7 && y>=0 && y<=7){
            if(Data[y][x] == check){
                check_count++;
                x += search_mode[i][0];
                y += search_mode[i][1];
            }else if(Data[y][x] == turn && check_count > 0){
                check_legitimate = true;
                break;
            }else{
                break;
            }
        }

最後做個結合
判斷是不是合法位置的演算法就好了

function check_put_legitimate(X, Y, turn){
    if (X < 0 || X > 7 || Y < 0 || Y > 7 || Data[Y][X] != " "){
        return [false, [-2], [0]];
    }
    // setting
    let check = turn == "O" ? "X" : "O";
    let legitimate = false;
    let mode = [-1];
    let count = [0];
    // check
    for(let i = 0; i < search_mode.length; i++){
        let x = X + search_mode[i][0];
        let y = Y + search_mode[i][1];
        let check_count = 0;
        let check_legitimate = false;
        while (x>=0 && x<=7 && y>=0 && y<=7){
            if(Data[y][x] == check){
                check_count++;
                x += search_mode[i][0];
                y += search_mode[i][1];
            }else if(Data[y][x] == turn && check_count > 0){
                check_legitimate = true;
                break;
            }else{
                break;
            }
        }
        if(check_legitimate){
            legitimate = true;
            mode.push(i);
            count.push(check_count);
        }
    }

    return [legitimate, mode, count];
}

下棋

確認他的位置是合法之後我們就要來下棋拉
首先我用一個二微陣列儲存資料

let Data = [ // white;O black;X
    // 0    1    2    3    4    5    6    7
    [" ", " ", " ", " ", " ", " ", " ", " "],// 0
    [" ", " ", " ", " ", " ", " ", " ", " "],// 1
    [" ", " ", " ", " ", " ", " ", " ", " "],// 2
    [" ", " ", " ", "O", "X", " ", " ", " "],// 3
    [" ", " ", " ", "X", "O", " ", " ", " "],// 4
    [" ", " ", " ", " ", " ", " ", " ", " "],// 5
    [" ", " ", " ", " ", " ", " ", " ", " "],// 6
    [" ", " ", " ", " ", " ", " ", " ", " "] // 7
]

接下來是寫入檔案

function play(X, Y, turn, mode, count){
}

還記得我們上次回傳值是什麼嗎
是不是[是否合法, [方向], [夾心個數]]
是否合法的部份我們留給判斷式 如果成立就執行我們這個程式
也就是下棋

function play(X, Y, turn, mode, count){
    for(let i = 1; i < mode.length; i++){
        let x = X + search_mode[mode[i]][0];
        let y = Y + search_mode[mode[i]][1];
}

依序從記錄的方向提出來做翻棋
並且設定x,y為現在座標
然後就把對手的棋改成我方的棋

function play(X, Y, turn, mode, count){
    for(let i = 1; i < mode.length; i++){
        let x = X + search_mode[mode[i]][0];
        let y = Y + search_mode[mode[i]][1];
        for(let j = 0; j < count[i]+1; j++){
            Data[y][x] = turn;
            x += search_mode[mode[i]][0];
            y += search_mode[mode[i]][1];
        }
    }
}

這樣下棋的部分就解決了

結束了?

最後一個難點是判斷結束以及pass
還記得我們前面提到黑白棋的規則嗎

  1. 如果你無法下棋的話，你該局就pass
  2. 如果雙方都無法下棋則結束遊戲，場上棋多者勝

所以首先先來做判斷單人的
兩人都不能下的話就只是執行兩次而已

那我們的想法也很簡單喔
什麼叫做都不能下
是不是就是所有位置都是不合法位置
ㄟ! 判斷合不合法
不就是剛剛寫的嗎
所以我們就抓每一格沒有旗子的格子來判斷就行了
(這不是最省時的方法，最省時的方法應是找出邊緣才拿去判斷
可是我們棋盤最多就8*8-4格而已，所以意義不大。暴力破解即可)

function check_end(turn){
    let end = true;
    for(let i = 0; i < 8; i++){
        for(let j = 0; j < 8; j++){
            if(Data[i][j] == " "){
                if(check_put_legitimate(j, i, turn)[0]){
                    end = false;
                }
            }
        }
    }
    return end;
}

最後在輸出結果就好

誰贏了

當兩人都不能下的時候就結束了
棋子最多的獲勝
所以就是數棋子拉
這邊也是很簡單
就每個都看一下 真●計數

function check_win(){
    let count = [0, 0];
    for(let i = 0; i < 8; i++){
        for(let j = 0; j < 8; j++){
            if(Data[i][j] == "O"){
                count[0]++;
            }else if(Data[i][j] == "X"){
                count[1]++;
            }
        }
    }
    return count[0] > count[1] ? "white" : "black";
}

恭喜到這邊你已經會做黑白棋了
那下面就用今天所學的做成一個網頁跑的遊戲吧

範例程式

/*
* AUTHOR rlongdragon
* DATE   2022-10-08
* VISON  1.2
* 
* this probject used copilot
*/



let Data = [ // white;O black;X
    // 0    1    2    3    4    5    6    7
    [" ", " ", " ", " ", " ", " ", " ", " "],// 0
    [" ", " ", " ", " ", " ", " ", " ", " "],// 1
    [" ", " ", " ", " ", " ", " ", " ", " "],// 2
    [" ", " ", " ", "O", "X", " ", " ", " "],// 3
    [" ", " ", " ", "X", "O", " ", " ", " "],// 4
    [" ", " ", " ", " ", " ", " ", " ", " "],// 5
    [" ", " ", " ", " ", " ", " ", " ", " "],// 6
    [" ", " ", " ", " ", " ", " ", " ", " "] // 7
]
let search_mode = [
    [0, 1], [1, 0], [0, -1], [-1, 0], // down, right, up, left
    [1, 1], [1, -1], [-1, 1], [-1, -1] // down-right, down-left, up-right, up-left
]

// function
function check_put_legitimate(X, Y, turn){
    if (X < 0 || X > 7 || Y < 0 || Y > 7 || Data[Y][X] != " "){
        return [false, [-2], [0]];
    }
    // setting
    let check = turn == "O" ? "X" : "O";
    let legitimate = false;
    let mode = [-1];
    let count = [0];
    // check
    for(let i = 0; i < search_mode.length; i++){
        let x = X + search_mode[i][0];
        let y = Y + search_mode[i][1];
        let check_count = 0;
        let check_legitimate = false;
        while (x>=0 && x<=7 && y>=0 && y<=7){
            if(Data[y][x] == check){
                check_count++;
                x += search_mode[i][0];
                y += search_mode[i][1];
            }else if(Data[y][x] == turn && check_count > 0){
                check_legitimate = true;
                break;
            }else{
                break;
            }
        }
        if(check_legitimate){
            legitimate = true;
            mode.push(i);
            count.push(check_count);
        }
    }

    return [legitimate, mode, count];
}

function play(X, Y, turn, mode, count){
    Data[Y][X] = turn;
    for(let i = 1; i < mode.length; i++){
        let x = X + search_mode[mode[i]][0];
        let y = Y + search_mode[mode[i]][1];
        for(let j = 0; j < count[i]; j++){
            Data[y][x] = turn;
            x += search_mode[mode[i]][0];
            y += search_mode[mode[i]][1];
        }
    }
}

function print(){
    let str = "  0 1 2 3 4 5 6 7";
    for(let i = 0; i < 8; i++){
        str += "\n" + i + " ";
        for(let j = 0; j < 8; j++){
            str += Data[i][j] + "|";
        }
    }
    console.log(str);
}

function check_end(turn){
    let end = true;
    for(let i = 0; i < 8; i++){
        for(let j = 0; j < 8; j++){
            if(Data[i][j] == " "){
                if(check_put_legitimate(j, i, turn)[0]){
                    end = false;
                }
            }
        }
    }
    return end;
}

function check_win(){
    let count = [0, 0];
    for(let i = 0; i < 8; i++){
        for(let j = 0; j < 8; j++){
            if(Data[i][j] == "O"){
                count[0]++;
            }else if(Data[i][j] == "X"){
                count[1]++;
            }
        }
    }
    return count[0] > count[1] ? "white" : "black";
}

// main
print();
let turn = "O";
let count = 0;
while(true){
    let put = false;
    // wait input
    let input = prompt(`is ${turn == "O" ? "white" : "black"} turn input X Y`);
    let X = parseInt(input.split(" ")[0]);
    let Y = parseInt(input.split(" ")[1]);

    // check put
    let check = check_put_legitimate(X, Y, turn);
    if(check[0]){
        put = true;
        play(X, Y, turn, check[1], check[2]);
    }
    if(put){
        print();
        turn = turn == "O" ? "X" : "O";
        if(check_end(turn)){
            turn = turn == "O" ? "X" : "O";
            if (check_end(turn)){
                break;
            }
        }
    }
}

下期預告

棋類遊戲-黑白棋實作篇
>_將網頁遊戲做到arcade


上一篇
Arcade再進化-空島跳躍者(4)
下一篇
Arcade再進化-射擊遊戲(4)
系列文
玩game學打code。街機程式設計再進化。微軟Arcade 共 30 篇
  1. 26
    Arcade再進化-橫向捲軸遊戲(4)
  2. 27
    Arcade再進化-空島跳躍者(5)
  3. 28
    Arcade再進化-社群遊戲大集合(上)
  4. 29
    Arcade也能學演算法Ouo!? 演算法遊戲(5)
  5. 30
    Arcade再進化-社群遊戲大集合(下)
完整目錄
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1064 組
團體組數
40 組
累計文章數
22200 篇
完賽人數
602 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙